package com.wang.leetcode;

/**
 * @Author: along
 * @Create: 2021/9/7
 * @Description:分割平衡字符串
 * 在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
 * 给你一个平衡字符串s，请你将它分割成尽可能多的平衡字符串。
 * 注意：分割得到的每个字符串都必须是平衡字符串。
 * 返回可以通过分割得到的平衡字符串的 最大数量 。
 */

public class Solution1121 {
    /**
     *
     * @param s
     * @return res
     * 根据题意，对于一个平衡字符串 ss，若 ss 能从中间某处分割成左右两个子串，
     * 若其中一个是平衡字符串，则另一个的L和R字符的数量必然是相同的，所以也一定是平衡字符串。
     * 为了最大化分割数量，我们可以不断循环，每次从 ss 中分割出一个最短的平衡前缀，
     * 由于剩余部分也是平衡字符串，我们可以将其当作 ss 继续分割，直至 ss 为空时，结束循环。
     */
    public int balancedStringSplit1(String s) {
        //贪心
        //res 返回结果 d维护L和R字符的数量之差
        int res = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if(ch == 'L') {
                ++d;
            }
            else {
                --d;
            }
            if(d == 0) {
                ++res;
            }
        }
        return  res;
    }
    public int balancedStringSplit2(String s) {
        int res = 0, cL = 0, cR = 0;
        char[] ch = s.toCharArray();
        for (int i = 0; i < s.length(); ++i) {
            if(ch[i] == 'L') {
                ++cL;
            }
            if(ch[i] == 'R') {
                ++cR;
            }
            if(cL != 0 && cR != 0 && cL == cR) {
                res++;
            }
        }
        return res;
    }
}
